#define _CRT_SECURE_NO_WARNINGS 1
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include<math.h>
#include<stdlib.h>
#include<stdio.h>
#include<unordered_map>
#include<queue>
#include<stack>
#include <functional>
#include <memory>
using namespace std;

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int n = matrix.size(), m = matrix[0].size();
        vector<vector<int>> dp(n, vector<int>(m));
        for (int i = 0; i < m; i++)
            dp[0][i] = matrix[0][i];
        for (int i = 1; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                int tmp;
                tmp = dp[i - 1][j];
                if (j - 1 >= 0) tmp = min(tmp, dp[i - 1][j - 1]);
                if (j + 1 < m) tmp = min(tmp, dp[i - 1][j + 1]);
                dp[i][j] = tmp += matrix[i][j];
            }
        }
        int ret = dp[n - 1][0];
        for (int i = 0; i < m; i++)
            ret = min(ret, dp[n - 1][i]);
        return ret;
    }
};

int main()
{
    vector<int> in(30, -1);
	return 0;
}